#!/usr/bin/env python
import sys, math, random
from mpi4py import MPI
import numpy as np
import spacesaving as ss


class CRoP :
	def __init__(self, eps,rank,p):
		self.h1, self.h2 = {},{} # hashtables for i,j indices of matrices
		self.eps = eps
		self.SS = ss.SpaceSavingHashBuffer(eps, int(1/eps))
		self.p = p
		self.rank = rank
		self.p_dist = np.zeros((self.p,), dtype=np.int)

	def val(self,h, x, hi):
		if not(x in h):
			random.seed(x + hi) # http://docs.python.org/library/random.htm. Hashvalue of x is determined by the random.seed
			h[x] = int(random.random() * self.p)
		print "x={0} h[x]={1}".format(x,h[x]);
		return h[x]

	def do_outer_product(self,h1val, h2val, h1_counts) :
		for b_item in h2val :
			#print "size", int (len(A) * b_item[2] / 10 + 0.5)
			a_idx = (self.p + self.rank - b_item[0]) % self.p # calculate the value of "a" for which (h1(a_i) + h2(b_j)) % p = rank
			ab_range = h1val[h1_counts[a_idx]:h1_counts[a_idx + 1]] # get range of items from A
			if len(ab_range) == 0 : continue # processor rank not responsible for this multiplication

			self.p_dist[self.rank] += len(ab_range) # debugging

			for a_item in ab_range:
				self.SS.add(((a_item[1],b_item[1]), a_item[2] * b_item[2]))

	def crop(self,a_col, b_row) :
		hc_1 = [0 for x in range(self.p)]
		h1val, h2val, = [], []
		for a_i, w in enumerate(a_col) :
			if w == 0.0 :
				continue
			h = self.val(self.h1, a_i, 0)
			hc_1[h] += 1
			h1val.append((h,a_i,w))
		for b_j, w in enumerate(b_row) :
			if w == 0.0 :
				continue
			h = self.val(self.h2,b_j,1)
			h2val.append((h,b_j,w))

		hc_1 = list(np.cumsum(hc_1))
#		print "h1_counts", hc_1
		hc_1.insert(0,0)
		h1val.sort()
		self.do_outer_product(h1val, h2val, hc_1)

	def get_dist(self):
		return self.p_dist

	def get_summary(self,type):
		return self.SS.get_summary(type)

	def get_hash_tables(self):
		return (self.h1,self.h2)
def main():

	crop = CRoP(0.125, 1,2)
	#A = B = C = np.load('../np_mat_2x2.npy')
	A = open('./test_matrix.in');
	#print np.dot(A,B)
	A = A.readlines();

	for i, line in enumerate(A) :
		l = list(map(lambda x: float(x), line.strip().split(' ')))
		crop.crop(l,l)
	print crop.p_dist;
	#while c < len(A[0]) :
	#	crop.crop(A[c,:],B[c,:])
#		c+=1

	#print crop.get_summary('list')

main()